SP694 DISUBSTR - Distinct Substrings

这道题用后缀自动机可以暴力解决。

建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG\text{DAWG}dpdpdp[u]dp[u]表示包含转移uu的子串数量,很容易列出转移式:

dp[u]=vson[u]dp[v]dp[u]=\sum_{v \in son[u]} dp[v]

注意虽然是一个DAG\text{DAG},但是我们并不需要把图建出,只需要用拓扑序dpdp就可以了。

注意,此题不一定是小写字母!!!

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 1000 , MAXK = 256;
struct Suffix_Automaton {
	int Root , Size , Last , Maxlen[ 2 * MAXN + 5 ]; 
	int Trans[ 2 * MAXN + 5 ][ MAXK + 5 ] , Link[ 2 * MAXN + 5 ];
	long long dp[ 2 * MAXN + 5 ];
	
	Suffix_Automaton( ) { Root = Size = Last = 1; }
	
	void Copy( int u , int v ) {
		for( int i = 1 ; i <= MAXK ; i ++ )
			Trans[ u ][ i ] = Trans[ v ][ i ];
	}
	void Extend( int chr ) {
		int Newnode = ++ Size , u = Last;
		Maxlen[ Newnode ] = Maxlen[ u ] + 1;
		
		for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
			Trans[ u ][ chr ] = Newnode;
		
		if( !u ) Link[ Newnode ] = 1;
		else {
			int v = Trans[ u ][ chr ];
			
			if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
			else {
				int w = ++ Size;
				Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
				for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
				Link[ w ] = Link[ v ];
				Link[ v ] = Link[ Newnode ] = w;	
			}
		}
		Last = Newnode;
	}
	void Build( char *str ) {
		Root = Size = Last = 1;
		memset( Trans , 0 , sizeof( Trans ) );
		memset( Link , 0 , sizeof( Link ) );
		memset( dp , 0 , sizeof( dp ) ); 
		memset( tot , 0 , sizeof( tot ) ); 
		
		int len = strlen( str );
		for( int i = 0 ; i < len ; i ++ )
			Extend( str[ i ] );
		Sort( );
	}
	
	int tot[ 2 * MAXN + 5 ] , Topu[ 2 * MAXN + 5 ];
	void Sort( ) {
		for( int i = 1 ; i <= Size ; i ++ ) tot[ Maxlen[ i ] ] ++;
		for( int i = 1 ; i <= Size ; i ++ ) tot[ i ] += tot[ i - 1 ];
		for( int i = 1 ; i <= Size ; i ++ ) Topu[ tot[ Maxlen[ i ] ] -- ] = i; 
	} 
	
	long long Dp( ) {
		for( int i = Size ; i >= 1 ; i -- ) { //深度从大到小
			int u = Topu[ i ];
			dp[ u ] = ( u > 1 );
			for( int k = 1 ; k <= MAXK ; k ++ )
				if( Trans[ u ][ k ] ) dp[ u ] += dp[ Trans[ u ][ k ] ]; 
		}
		return dp[ Topu[ Root ] ]; //这里写成dp[ Root ]也没有问题,起点的拓扑序一定是最大的
	}
}SAM;

int t;
char str[ MAXN + 5 ];

int main( ) {
	scanf("%d",&t);
	while( t -- ) {
		scanf("%s", str );
		SAM.Build( str );
		printf("%lld\n", SAM.Dp( ) );
	}
	return 0;
}